The present invention relates generally to content addressable memories (CAMs) and more particularly to a CAM having redundancy capabilities.
Content addressable memories (CAMs), also sometimes referred to as xe2x80x9cassociative memoriesxe2x80x9d, can provide rapid matching functions between a number of stored data values and an applied comparand value. A typical CAM can store data values in one or more CAM cell arrays. The CAM cell arrays can be configured into a number of entries, each of which can provide a match indication. In a compare (i.e., match) operation, the data values stored within the entries can be compared to the comparand value (also referred to as a xe2x80x9csearch keyxe2x80x9d). If a data value matches an applied comparand value, the corresponding entry can generate an active match indication. If a data value does not match an applied comparand value, the corresponding entry can generate an inactive match indication (signifying a xe2x80x9cmismatchxe2x80x9d) condition.
Among the many various types of CAMs are binary CAMs and ternary CAMs. Binary CAMs can compare exact bit values of a comparand to corresponding bits of the entries. Ternary CAMs can enable the masking of selected portions of the entries from a compare operation.
In many applications, the entries within a CAM may be continuously updated. Consequently, some conventional CAMs may include a xe2x80x9cstatusxe2x80x9d bit (sometimes referred to as a xe2x80x9cvalid/invalidxe2x80x9d or xe2x80x9coccupied/unoccupiedxe2x80x9d bit). A status bit can be stored in one or more CAM cells in an entry. A status bit can have a xe2x80x9cvalidxe2x80x9d logic state that can indicate an entry that stores usable data. A status bit can also have an xe2x80x9cinvalidxe2x80x9d logic state that can indicate that the data stored within contains data that should no longer be used in a compare operation.
Various aspects of CAM operations are described in co-pending U.S. patent application Ser. No. 09/440,682 titled CONTENT ADDRESSABLE MEMORY HAVING PRIORITIZATION OF UNOCCUPIED ENTRIES (Sywyk et al ""682). Sywyk et al. ""682 discusses status bits and CAM entry priority. In addition, Sywyk et al ""682 shows a novel way of determining which of the various entries is a xe2x80x9cnext freexe2x80x9d entry. The contents of this patent application are incorporated by reference herein.
CAMs are typically manufactured as stand alone integrated circuits or may also be included within (embedded) as one portion of a larger integrated circuit. Thus, like most any other integrated circuits, CAMs may be susceptible to manufacturing defects.
In a typical manufacturing process, integrated circuits may be formed as xe2x80x9cdicexe2x80x9d on a semiconductor wafer. The wafer may be sliced into individual dice, and each die may then be packaged. In a manufacturing process, defects may be formed on the wafer, due to uncontrollable process variation, or the like. Consequently, a wafer yield (percentage of xe2x80x9cgoodxe2x80x9d dice on a wafer) may be less than 100%.
In conventional random access memories (RAMs) and read-only-memories (ROMs), one way to address defects has been to include redundant circuit elements. For example, a typical RAM may include memory cells that are addressable according to a row and column location. If a memory cell was defective, the column or row containing the defective memory cell could be replaced by a redundant column or redundant row. Then, when a RAM address corresponds to the defective memory cell, the redundant column or redundant row could be accessed instead of the column or row containing the defective memory cell. Further, the column or row containing the defective memory cell can be deactivated. In this way, a defective memory cell can be replaced by a redundant memory cell. Such an approach can result in increased yield in an overall manufacturing process.
While redundant circuit elements have been included in RAMs and ROMs, such approaches in CAMs can be more problematic. To better understand the difficulties involved in CAM redundancy schemes, a conventional CAM that does not include redundant elements will now be described.
Referring now to FIG. 6, a conventional CAM 600 may include a number of rows 602-0 to 602-n. Each row (602-0 to 602-n) includes memory cells 604 that may store data values, and thereby form a CAM entry. Memory cells 604 may be binary and/or ternary CAM cells, for example.
Like a conventional RAM or ROM, a CAM 600 may include a row decoder 606. A ROW decoder 606 can enable a row (602-0 to 602-n) to be accessed by way of word lines (WL0 to WLn). Such accesses can allow data values to be read from or written to the rows (602-0 to 602-n).
However, unlike a conventional RAM or ROM, each row (602-0 to 602-n) may also provide a match indication on match line (ML0 to MLn). Such match indications may then be prioritized by a priority encoder 608. A priority encoder 608 can activate a ROM input (ROM0 to ROMn) that corresponds to a highest priority match. As but one example, if lower numbered match lines have highest priority, in the event that match lines ML0 and ML2 were both activated, only ROM0 would be activated. If however, match lines ML2 and MLn were activated, only ROM2 would be activated. An activated ROM input (ROM0 to ROMn) may then encode into an index value INDEX, which can be output from a ROM 610.
As can be shown by FIG. 6, circuits for prioritizing a match indication (M0 to Mn) can complicate approaches to redundancy. In particular, if a redundant row was provided to replace a non-redundant row (602-0 to 602-n), it is not clear how the redundant row could have the same priority as the replaced non-redundant row.
It would be desirable to arrive at some way of implementing a redundancy scheme in a CAM, particularly one that could provide row redundancy in a CAM.
According to the disclosed embodiments, a content addressable memory (CAM) includes redundant rows that may be used to replace ordinary (i.e., non-redundant) rows. Redundant rows may provide redundant match indications while ordinary rows may provide ordinary match indications. Switching circuits may provide either a redundant match indication or an ordinary match indication as an input to a priority encoder. In this way, a redundant row may have the same priority as the ordinary row that it replaces.
According to one aspect of the embodiments, multiplexer circuits can receive redundant and ordinary match indications, and provide one or the other as an output according to a redundant enable signal.
According to another aspect of the embodiments, a redundant enable signal may be generated by a redundancy indication circuit that may include nonvolatile circuit elements, such as fusible links.
According to another aspect of the embodiments, multiple redundant rows may replace multiple ordinary rows.
According to another aspect of the embodiments, redundant rows may further include a redundant status indication and ordinary rows may include ordinary status indications. If redundant rows are used to replace ordinary rows, redundancy status indications from the redundant rows may be supplied to a priority encoder by mode multiplexers.
According to another aspect of the embodiments, a CAM may include redundancy multiplexers that select between redundant and ordinary indications and mode multiplexers that select between match and status indications.